In digital circuits, metastable signals have voltages strictly between logical 0 and logical 1, breaking the abstraction of Boolean logic. Unfortunately, any way of reading a signal from an unsynchronized clock domain or performing an analog-to-digital conversion incurs the risk of a metastable result; no physical implementation of a digital circuit can deterministically avoid, resolve, or detect metastability (L. R. Marino. General theory of metastable operation. IEEE Transactions on Computers, 30(2):107, 115, February 1981).
Traditionally, the only countermeasure is to write a potentially metastable signal into a synchronizer—a bistable storage element like a flip-flop—and wait. Synchronizers exponentially decrease the odds of maintained metastability over time, i.e., the waiting time determines the probability to resolve to logical 0 or 1. Accordingly, this approach delays subsequent computations and does not guarantee success.
A promising alternative is to run a fault-tolerant clock synchronization algorithm, like the one by Lynch and Welch (J. Lundelius Welch and N. A. Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1{36, 1988), preserving the benefits of multiple clock domains while removing the need for synchronizers.
The algorithm by Welch and Lynch is widely applied, e.g. in the Time-Triggered Protocol (TP) and FlexRay clock synchronization protocols. While the software/hardware based implementations of TTP and FlexRay achieve a precision in the order of one millisecond, higher operating frequencies ultimately require a pure hardware implementation.
All known implementations, however, synchronize potentially metastable inputs before computations—a technique that becomes less reliable with increasing operating frequencies, since less time is available for metastability resolution. Moreover, classical bounds for the Mean Time Between Failures (MTBF) for metastable upsets assume a uniform distribution of input transitions; this is not guaranteed to be the case in clock synchronization, since the goal is to align clock ticks. Either way, synchronizers do not deterministically guarantee stabilization, and errors are bound to happen eventually when n clocks take n(n−1) samples at, e.g., 1 GHz.
It is therefore an object of the present invention to provide a method and corresponding digital circuit for efficient and dependable clock synchronization in hardware that do not depend on metastability-free inputs and thus does not suffer from system failures induced by metastable upsets.